package leetcode.editor.cn.dsa13_mergesort;
// 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
// 每行中的整数从左到右按升序排列。
// 每行的第一个整数大于前一行的最后一个整数。 
//
// 示例 1： 
// 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
// 输出：true
// 
// 示例 2：
// 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
// 输出：false
//
// 示例 3： 
// 输入：matrix = [], target = 0
// 输出：false
//
// 提示： 
// m == matrix.length
// n == matrix[i].length 
// 0 <= m, n <= 100 
// -104 <= matrix[i][j], target <= 104 
// 
// Related Topics 数组 二分查找 
// 👍 285 👎 0

public class SearchA2dMatrix74 {
    public static void main(String[] args) {
        Solution solution = new SearchA2dMatrix74().new Solution();
        int[][] arr = {{1,3,5,7},{10,11,16,20},{23,30,34,50}};
        System.out.println(solution.searchMatrix(arr, 3)); //true
        System.out.println(solution.searchMatrix(arr, 34)); //true
        System.out.println(solution.searchMatrix(arr, 13)); //false
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 该二维数组本质就是一个升序的一维数组，使用二分搜索只需注意索引转换即可
        public boolean searchMatrix(int[][] matrix, int target) {
            int m = matrix.length; if(m == 0) return false; // 行数
            int n = matrix[0].length; if(n == 0) return false; // 列数
            int start = 0, end = (m * n) - 1;
            while (start <= end) {
                int mid = (start + end) / 2;
                // index与i,j的转换关系，i=index/n，j=index%n
                int midNum = matrix[mid/n][mid%n];
                if (midNum == target) return true;
                if (midNum < target) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}